#include <malloc.h>
#include "header.h"
#include "securec.h"
void inorder(struct TreeNode *root, int *res, int *resSize) {
    if (!root) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)++] = root->val;
    inorder(root->right, res, resSize);
}
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 501);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
}
void getNum(char str[], char retStrArr[100][10], int *count) {    //1.使用strtok()实现分割
    char test[100] = {0};
    strncpy_s(test, sizeof(test) - 1, (str + 1), strlen(str) - 2);
    char *tmp = strtok(test, " ,");
    if (!tmp) {
        *count = 0;
        return;
    } else {
        strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), tmp);
    }
    while (tmp != NULL) {
        tmp = strtok(NULL, " ,");
        if (NULL == tmp) {
            break;
        }
        if (strcmp(tmp, "null") == 0) {
            strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), "-1");
        } else {
            strcpy_s(retStrArr[(*count)++], sizeof(retStrArr[*count]), tmp);
        }
    }
}
struct List {
    struct TreeNode *cur;
    struct List *next;
};
void bfsBuildTree(struct TreeNode *root, int numsArr[], int count) {
    int index = 0;
    int start = 1;
    struct TreeNode *nodes[256] = {0};
    int curCount = 1;
    int tmpCount = 0;
    nodes[0] = root;
    int end = 1;
    while (start < count) {
        for (int i = 0; i < curCount && start < count; ++i) {
            struct TreeNode *node = (struct TreeNode *) nodes[index + i];
            if (start < count) {
                if (numsArr[start] != -1) {
                    node->left = malloc(sizeof(struct TreeNode));
                    node->left->left = NULL;
                    node->left->right = NULL;
                    node->left->val = numsArr[start++];
                    tmpCount++;
                    nodes[end++] = node->left;
                } else {
                    start++;
                }
            }
            if (start < count) {
                if (numsArr[start] != -1) {
                    node->right = malloc(sizeof(struct TreeNode));
                    node->right->left = NULL;
                    node->right->right = NULL;
                    node->right->val = numsArr[start++];
                    tmpCount++;
                    nodes[end++] = node->right;
                } else {
                    start++;
                }
            }
        }
        index += curCount;
        curCount = tmpCount;
        tmpCount = 0;
    }
//    struct List *tmp = list;
//
//    struct List *dummy = malloc(sizeof (struct  List));
//    struct List *curNode = dummy;
//
//    while (list->cur && start < count) {
//        int tmpCount = 0;
//        for (int i = 0; i < curCount; ++i) {
//            // 添加左子树节点
//            if (list->cur->left && start < count) {
//                list->cur->left = malloc(sizeof (struct TreeNode));
//                list->cur->left->val = numsArr[start++];
//                list->cur->left->left= NULL;
//                list->cur->left->right = NULL;
////                curNode->next->cur = list->cur->left;
//                if (list->cur->left->val != -1) {
//                    curNode->cur = list->cur->left;
//                    curNode->next = malloc(sizeof (struct List));
//                    curNode =  curNode->next;
//                    curNode->next = NULL;
//                    tmpCount++;
//                }
//            }
//            // 添加右子树节点
//            if (list->cur->right && start < count) {
//                list->cur->right = malloc(sizeof (struct TreeNode));
//                list->cur->right->val = numsArr[start++];
//                list->cur->right->left= NULL;
//                list->cur->right->right = NULL;
////                curNode->next->cur = list->cur->right;
//
//                if (list->cur->right->val != -1) {
//                    curNode->cur = list->cur->right;
//                    curNode->next = malloc(sizeof (struct List));
//                    curNode = curNode->next;
//                    curNode->next = NULL;
//                    tmpCount++;
//                }
//            }
//            list = list->next;
//        }
//        curCount = tmpCount;
//    }
}
int main() {
    printf("%s", "  start");
    char str[] = "[1,null,2,3,6, 4,5,7,8]";
    printf("\n\n\n%s\n", "start strtok string.");
    int count = 0;
    char retStrArr[100][10] = {0};
    getNum(str, retStrArr, &count);
    int numArr[9] = {0};
    for (int i = 0; i < count; ++i) {
        printf("%s\n", retStrArr[i]);
        numArr[i] = atoi(retStrArr[i]);
    }
    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = numArr[0];
    root->left = NULL;
    root->right = NULL;
    bfsBuildTree(root, numArr, count);
    int returnSize = 0;
    int *ret = inorderTraversal(root, &returnSize);
    for (int i = 0; i < returnSize; ++i) {
        printf("%d ", ret[i]);
    }
//    [1,4,3,5,2,7,6,8]
}
